package problem221_Maximal_Square;

/**
 * dp[x][y]表示以（x,y）作為右下角點的正方形的边长，
 * dp[x][y]=min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1])+1;
 * 
 * @author I321035
 *
 */
public class Solution {
	public int maximalSquare(char[][] matrix) {
		if(matrix.length==0)
			return 0;
		int[][] dp=new int[matrix.length][matrix[0].length];
		int max=0;
		for(int i=0;i<matrix.length;i++){
			if(matrix[i][0]=='1'){
				dp[i][0]=1;
				max=1;
			}
		}
		for(int i=0;i<dp[0].length;i++){
			if(matrix[0][i]=='1'){
				dp[0][i]=1;
				max=1;
			}
		}
		for(int i=1;i<dp.length;i++){
			for(int j=1;j<dp[i].length;j++){
				if(matrix[i][j]=='0')
					dp[i][j]=0;
				else
					dp[i][j]=Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
				max=Math.max(max, dp[i][j]);
			}
		}
		return max*max;
	}
}
